package com.lik.javadeep.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

public class BinTreeTest {
    /**
     * @param args
     */
    public static void main(String[] args) throws InterruptedException {

        BinNode five = new BinNode(5);
        five.setLeftChild(new BinNode(7));

        BinNode four = new BinNode(4);
        four.setRightChild(new BinNode(6));

        BinNode third = new BinNode(3);
        third.setLeftChild(four);
        third.setRightChild(five);

        BinNode root = new BinNode(1);
        root.setLeftChild(new BinNode(2));
        root.setRightChild(third);

        // preTravel(root);
        // inOrderedTravel(root);
        // traverseLevel(root);
        // postOrderTraverse(root);
        simplePostOrder(root);
    }

    /**
     * 先序遍历-左侧链法
     *
     * @param root
     */
    private static void preTravel(BinNode root) {
        if (root == null) {
            System.out.println("树为空");
            return;
        }

        // 辅助栈
        Stack<BinNode> stack = new Stack<>();
        BinNode current = root;

        while (true) {
            //
            visitAlongLeftAndPushRc(current, stack);

            if (stack.empty()) break;
            current = stack.pop();

        }
        // // 访问元素
        // System.out.println(current.getData());


    }

    /**
     * 沿着左侧链访问，并且将 右孩子 入栈
     *
     * @param current
     * @param stack
     */
    private static void visitAlongLeftAndPushRc(BinNode current, Stack<BinNode> stack) {
        while (current != null) {

            // 访问元素
            System.out.println(current.getData());

            stack.push(current.getRightChild());
            current = current.getLeftChild();

        }
    }

    private static void inOrderedTravel(BinNode root) {
        Stack<BinNode> stack = new Stack<>();

        BinNode current = root;
        while (true) {
            goAlongLeftAndPush(current, stack);
            if (stack.empty()) break;

            current = stack.pop();
            // 访问元素
            if (current != null) {
                System.out.println(current.getData());
            }

            current = current.getRightChild();
        }
    }

    /**
     * 沿着左侧链，将 右孩子 入栈
     *
     * @param current
     * @param stack
     */
    private static void goAlongLeftAndPush(BinNode current, Stack<BinNode> stack) {
        while (current != null) {
            stack.push(current);

            current = current.getLeftChild();
        }
    }

    /**
     * 层次遍历
     */
    private static void traverseLevel(BinNode root) throws InterruptedException {
        ArrayBlockingQueue<BinNode> queue = new ArrayBlockingQueue<>(100);
        queue.add(root);
        while (!queue.isEmpty()) {
            BinNode poll = queue.poll();

            // 访问元素
            System.out.println(poll.getData());

            if (poll.getLeftChild() != null) {
                queue.put(poll.getLeftChild());
            }
            if (poll.getRightChild() != null) {
                queue.put(poll.getRightChild());
            }

        }
    }

    /**
     * 后序遍历
     */
    private static void postOrderTraverse(BinNode root) {
        Stack<BinNode> stack = new Stack<>();
        stack.push(root);


        while (!stack.empty()) {
            // 出栈，先沿着左侧链
            BinNode pop = stack.pop();
            goAlongLeftAndPushLc(pop, stack);

        }


    }

    private static void goAlongLeftAndPushLc(BinNode current, Stack<BinNode> stack) {
        BinNode tempParent = current;

        while (true) {
            // 没有左子树
            if (current.getLeftChild() == null) {

                // 也没有右子树
                if (current.getRightChild() == null) {
                    stack.push(tempParent);
                } else {
                    stack.push(current.getRightChild());
                }
            } else {
                stack.push(current.getLeftChild());
                current = current.getLeftChild();
                tempParent = current;
            }

        }
    }

    public static void p(BinNode root) {
        Stack<BinNode> stack = new Stack<BinNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            BinNode node = stack.pop();

            System.out.println(node.getData());

            if (node.getRightChild() != null) {
                stack.push(node.getRightChild());
            }

            if (node.getLeftChild() != null) {
                stack.push(node.getLeftChild());
            }
        }
    }

    /**
     * 简单好理解的前序遍历
     *https://blog.csdn.net/GSCurry/article/details/77993483?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.edu_weight&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.edu_weight
     * @param root 根节点
     */
    public static void simplePreOrder(BinNode root) {
        Stack<BinNode> stack = new Stack<BinNode>();
        if (root == null) {
            return;
        }
        stack.push(root);

        while (!stack.empty()) {
            BinNode node = stack.pop();
            // 访问元素
            System.out.println(node.getData());

            // 右子树 因为最后访问，所以先入栈
            if (node.getRightChild() != null) {
                stack.push(node.getRightChild());
            }

            if (node.getLeftChild() != null) {
                stack.push(node.getLeftChild());
            }
        }

    }

    /**
     * 简单好理解的后序遍历
     *https://blog.csdn.net/GSCurry/article/details/77993483?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.edu_weight&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.edu_weight
     * @param root 根节点
     */
    public static void simplePostOrder(BinNode root) {
        Stack<BinNode> stack = new Stack<BinNode>();
        List<BinNode> list = new ArrayList<>();
        if (root == null) {
            return;
        }
        stack.push(root);

        while (!stack.empty()) {
            BinNode node = stack.pop();
            // 收集元素
            list.add(node);

            // 左->右->根 , 反转就是根->右->左；即左是最后访问的

            if (node.getLeftChild() != null) {
                stack.push(node.getLeftChild());
            }

            if (node.getRightChild() != null) {
                stack.push(node.getRightChild());
            }
        }

        Collections.reverse(list);
        for (BinNode binNode : list) {
            System.out.println(binNode.getData());
        }
    }
}
